package LC;

/**
 * Given an array of non-negative integers, you are initially positioned at the first index of the array.
 * Each element in the array represents your maximum jump length at that position.
 * Determine if you are able to reach the last index.
 * For example:
 * A = [2,3,1,1,4], return true.
 * A = [3,2,1,0,4], return false.
 */
public class LC_055_JumpGame_DP_Greedy {
    public static void main(String[] args) {
        int[] a = {2, 3, 1, 1, 4};
        boolean f = Solution_2.canJump(a);
        System.out.println(f);
    }

    static class Solution {
        static boolean canJump(int[] nums) {
            int n = nums.length;
            int dp[] = new int[n];
            dp[0] = nums[0];
            //i表示位置，nums[i]表示能跳的步数
            for (int i = 1; i < n; i++) {
                //在上一步能跳的范围之内，就跳
                if (i <= dp[i - 1])
                    dp[i] = Math.max(dp[i - 1], i + nums[i]);
                else
                    //不在上一步能跳的范围之内
                    dp[i] = dp[i - 1];
            }
            return dp[n - 1] >= (n - 1);
        }
    }

    static class Solution_2 {
        static boolean canJump(int[] nums) {
            int n = nums.length;
            int maxJump = 0;
            for (int i = 0; i < n; i++) {
                //不在上一步能跳的范围之内或者越界
                if (i > maxJump || maxJump >= (n - 1))
                    break;
                maxJump = Math.max(maxJump, i + nums[i]);
            }
            return maxJump >= (n - 1);
        }
    }

}
